#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
//            opt(i - 1, j - 1)
//opt(i, j) = 
//            min(opt(i, j - 1), opt(i - 1, j)) + 1

int dist(string s1, string s2)
{
        int l1 = s1.length();
        int l2 = s2.length();
        vector<vector<int>> dp(l1 + 1, vector<int>(l2 + 1, 0));
        s1.insert(0, "0");
        s2.insert(0, "0");

        for(int i = 0; i < dp.size(); i++){
                dp[i][0] = i;
        }
        for(int i = 0; i < dp[0].size(); i++){
                dp[0][i] = i;
        }

        for(int i = 1; i <= l1; i++){
                for(int j = 1; j <= l2; j++){
                        if(s1[i] == s2[j]){
                                dp[i][j] = dp[i - 1][j - 1];
                        }else{
                                dp[i][j] = min({dp[i - 1][j], dp[i - 1][j - 1], dp[i][j - 1]}) + 1;
                        }
                }
        }

        return dp.back().back();
}

int main()
{
        string s1, s2;
        int n = 0;
        cin>>n;
        for(int i = 0; i < n; i++){
                cin>>s1>>s2;
                cout<<dist(s1, s2)<<endl;
        }
        return 0;
}
/*
3
abcdefg  abcdef
ab ab
mnklj jlknm

*/